package com.lds.offer.demo;

import java.util.Arrays;

/**
 * @description: 1320. 二指输入的的最小距离 - 力扣（LeetCode）
 * @author: lds
 * @create: 2022-10-06 08:28
 **/
public class Offer_1320_二指输入的的最小距离 {

    //https://leetcode.cn/problems/minimum-distance-to-type-a-word-using-two-fingers/

    /**
     * 动态规划求最优解（不会）
     *
     */
    public static void main(String[] args) {
        int agev = minimumDistance("AGEV");
        System.out.println(agev);
    }
    public static int minimumDistance(String word) {
        // 初始化
        int[][][] dp = new int[2][26][26];
        for (int i = 0; i < 26; i++) {
            Arrays.fill(dp[1][i], Integer.MAX_VALUE);
        }

        int ans = Integer.MAX_VALUE;
        char[] ca = word.toCharArray();
        // 遍历每个字母
        for (int i = 1; i <= word.length(); i++) {
            int v = ca[i - 1] - 'A';
            // 遍历上一个阶段左指键位
            for (int l = 0; l < 26; l++) {
                // 遍历上一个阶段右指键位
                for (int r = 0; r < 26; r++) {
                    // 判断上一个阶段的状态是否存在
                    if (dp[(i - 1) % 2][l][r] == Integer.MAX_VALUE) {
                        continue;
                    }
                    if (dp[(i - 1) % 2][l][r] != Integer.MAX_VALUE) {
                        // 移动左指
                        dp[i % 2][v][r] = Math.min(dp[i % 2][v][r], dp[(i - 1) % 2][l][r] + help(l, v));
                        // 移动右指
                        dp[i % 2][l][v] = Math.min(dp[i % 2][l][v], dp[(i - 1) % 2][l][r] + help(r, v));
                    }
                    if (i == word.length()) {
                        ans = Math.min(ans, dp[i % 2][v][r]);
                        ans = Math.min(ans, dp[i % 2][l][v]);
                    }
                }
            }
            // 重新初始化另外一个数组
            for (int l = 0; l < 26; l++) {
                for (int r = 0; r < 26; r++) {
                    dp[(i - 1) % 2][l][r] = Integer.MAX_VALUE;
                }
            }

        }
        return ans;
    }
    // 计算距离
    public static int help(int a, int b) {
        int x = a / 6, y = a % 6;
        int x2 = b / 6, y2 = b % 6;
        return (int)(Math.abs(x - x2)) + (int)(Math.abs(y - y2));
    }
}
